package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  计数排序   合适比较紧凑的数字类型数组
 *  根据数字定位一个索引， 基于数组对于索引上的元素进行计数
 *      时间复杂度   Ο(n+m)
 *      稳定性      不稳定
 */
public class CountSort {

    public static void main(String[] args) {

        int[] arr = {2,35,65,123,6,7,12,1,1};

        System.out.println(Arrays.toString(arr));

        // 统计数组中的最大和最小值
        int max = arr[0], min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min) {
                min = arr[i];
            }
        }
        // 创建一个计数数组
        int[] countArr = new int[max - min + 1];
        // 起始索引
        int vIndex = -min;
        // 计数
        for (int i = 0; i < arr.length; i++) {
            countArr[vIndex + arr[i]] ++;
        }
        // 排序
        for (int i = 0,j=0; i < arr.length; ) {
            if(countArr[j] != 0){
                arr[i] = j - vIndex;
                countArr[j]--;
                i++;
            }else {
                j++;
            }
        }

        System.out.println(Arrays.toString(arr));

    }
}
